package edu.bluebeanforum.sort;

public class Sort {

    public void quickSort (int[] array) {
        quick(array,0,array.length-1);
    }

    public void quick(int[] array, int start, int end) {
        if (start >= end) {
            return;
        }

        // 使用直接插入排序进行优化
        if (end-start+1 <= 15) {
//            System.out.println("直接插入排序了");
            quickWithInsert(array,start,end);
            return;
        }
        // 三数取中优化
        int mid = findMidIndex(array,start,end);
        swap(array,mid,start);

        int part = partition(array,start,end);

        quick(array,start,part-1);
        quick(array,part+1,end);

    }

    private int findMidIndex(int[] array, int start, int end) {
        int midIndex = ( start + end ) / 2;
        if (array[start] > array[end]) {
            // end  start
            if (array[midIndex] < array[end]) {
                // midIndex end start
                return end;
            } else if (array[midIndex] > array[start]) {
                // end start midIndex
                return start;
            } else {
                return midIndex;
            }
        } else {
            // start  end
            if (array[midIndex] < array[start]) {
                return start;
            } else if (array[midIndex] > array[end]) {
                return end;
            } else {
                return midIndex;
            }
        }
    }

    private void quickWithInsert(int[] array, int start, int end) {
        for (int i = start+1 ; i <= end; i++) {
            int tmp = array[i];
            int j = i - 1;
            for (; j >= 0; j--) {
                if (array[j] >= tmp) {
                    array[j+1] = array[j];
                } else {
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }

    // 霍尔法
    private int partition(int[] array, int left, int right) {
        int tmp = array[left];
        int tmpIndex = left; // 记录基准值的位置
        while (left < right) {
            // 右边找到比基准值小的值，这个值表示不应该在基准值右边
            while (left < right && array[right] >= tmp) {
                right--;
            }
            // 找到基准值左边比基准值大的值，表示该值不应该出现在左边
            while (left < right && array[left] <= tmp) {
                left++;
            }
            // 到这个位置表示left和right都指向了需要交换的位置
            swap(array,left,right);
        }
        // 这里表示left和right相遇了  就要交换基准值的位置和相遇位置的值
        swap(array,tmpIndex,left);
        return left;
    }

    private void swap(int[] array, int x, int y) {
        int tmp = array[x];
        array[x] = array[y];
        array[y] = tmp;
    }
}
